package com.hardydou.algorithm;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author ：hardy
 * @description：topK问题
 * @date ：Created in 2021/1/5
 * @Copyright ：Hardydou.com
 */
public class TopK {
    Queue<Item> queue;
    int k;

    public TopK(int k) {
        this.k = k;
        this.queue = new PriorityQueue<Item>(new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return o1.compareTo(o2);
            }
        });
    }

    public void add(Item item) {
        queue.add(item);
        if (queue.size() > k) {
            queue.poll();
        }
    }

    public Item[] find() {
        Item[] result = new Item[queue.size()];
        queue.toArray(result);
        return result;
    }

    static class Item<T> implements Comparable<Item<T>> {
        T value;
        int order;

        @Override
        public int compareTo(Item o) {
            return order - o.order;
        }

        public Item(T value, int order) {
            this.value = value;
            this.order = order;
        }

        public T getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "Item{" +
                    "value=" + value +
                    ", order=" + order +
                    '}';
        }
    }
}


